package code1.binary_tree;

/**
 * 原题链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/
 */
public class P701 {

    public void insert(TreeNode cur,TreeNode pre,int val,int type){
        if(cur==null){
            cur=new TreeNode(val);
            if(type==0){
                pre.left=cur;
            }else if(type==1){
                pre.right=cur;
            }
        }
        if(cur.val > val){
            insert(cur.left,cur,val,0);
        }else if(cur.val < val){
            insert(cur.right,cur,val,1);
        }else{
            return;     //要插入的值已存在，不能插入，直接返回
        }
    }


    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            root=new TreeNode(val);     //根节点为空
        }else if(root.val > val){
            insert(root.left,root,val,0);
        }else if(root.val < val){
            insert(root.right,root,val,1);
        }else{
            return null;    //要插入的值已存在，不能插入，直接返回
        }
        return root;
    }
}
